1. Field of the Invention
The present invention relates generally to point cloud data, and in particular, to a method, apparatus, and article of manufacture for pre-segmenting point cloud data to run real-time shape extraction faster.
2. Description of the Related Art
Point cloud shape/feature extraction is a highly desired technique to facilitate the computer aided design (CAD) workflow. CAD designers don't want to snap to point clouds but prefer to work with planes, corners, and center lines. Laser scanners sample a surface without any knowledge of what is being sampling. Snapping to inferred geometry in real-time is problematic—enough points need to be available to create a decent representation, and fitting geometry is computationally intensive (on a large and/or reduced set of points). Accordingly, what is needed is the capability to quickly and accurately extract shapes/features from a point cloud. To better understand these problems, a description of prior art point cloud systems may be useful.
Point clouds are often created by reality capture devices such as laser three-dimensional (3D) scanners that measure a large number of points (e.g., from thousands to many billions of points [3D coordinates]) on the surface of an object, and output a point cloud as a data file. The point cloud represents the visible surface of the object that has been scanned or digitized. With the increased usage of such reality capture devices, large point cloud data sets are more frequently created for consumption by design applications. The challenge that design software faces is visualizing and using this data efficiently in the applications. While the point cloud data set is often very large, the number of points an application is capable of handling for visualization and other needs is a small fraction—a few million points, for example. Prior art methods fail to provide the ability to process the massive volume of points, in real time (e.g., preserving a ten [10] frames per second or faster rate) to read a small fraction of points that have the property of accurately representing the original data set without loss of detail or information that causes misrepresentation of the original data.
Point cloud visualization and applications are increasingly important in design, especially due to the decrease in the price point of the technology. Point clouds can contain an enormous number of points. One of the major challenges is representing the set of points while providing the ability to extract a small subset that is highly representative of the spatial region of interest.
As described above, a point cloud is created using a laser beam/scanner that scans objects/surfaces to obtain millions of points. For example, an image scanner on top of a car that drives through a city may obtain millions upon millions of points. If such points are rendered in a certain environment, different viewpoints may be queried/requested and displayed to a user. However, with a point cloud, if a scene is rendered, the depth component may not map properly. As a result, a visualization of a point cloud may require one thousand (1000) times of overdraw before the correct visualization is achieved.
Prior art methodologies may attempt to select a subset of the points in a quick and efficient manner. One approach divides a volume of interest into equal size rectangular 3D cells. Each of the thousands of cells may contain millions of points. The issue arises as to how to determine how many and which points to select from/in a cell. Further, point cloud data resulting from a scanner may have various artifacts that are undesirable. Accordingly, there is a desire to eliminate the scanner artifact, to normalize the point selection, and to obtain a uniform distribution/real depiction of the distribution of the point cloud data regardless of the location of the scanner. Many prior art approaches have attempted to solve such problems. Such approaches range from nearest neighbor based approaches to frequency domain based approaches. Concepts of downsampling, borrowed from image processing techniques have also been incorporated in solutions to view large point data sets. Goals of some techniques include noise removal and optimal representation, at the expense of computation and with freedom to modify the original point set.
In addition, as described above, to facilitate CAD workflows, a CAD system may extract shapes/features from the points. It is desirable to perform such extraction in real time. If the extraction is attempted on a large set of points, it can be computationally intensive. However, if the extraction is attempted on a minimized set of points, the error rate increases (e.g., shape extraction/fitting may not be accurate and/or may not be possible due to an insufficient number/range of points). Accordingly, what is needed is a method and apparatus that reduces the number of points from a point cloud in order to properly, accurately, and efficiently extract shapes/features.